package com.mgq.algorithm.array;

import java.util.Arrays;

/**
 * 插入排序
 *
 * [2,1,3,4,5,3,8]
 * 第一次 0~1
 * 2,1 交换
 * [1,2,3,4,5,3,8]
 * 第二次 0~2
 * 3和2比, 3大于2,不交换
 * [1,2,3,4,5,3,8]
 * 第三次
 * 4和3比.不交换
 * 第四次
 * 第五次
 * 5和3,比较
 * [1,2,3,4,3,5,8]
 * 3和4再比
 * [1,2,3,3,4,5,8]
 * 3和3再比.终止
 * [1,2,3,3,4,5,8]
 */
public class InsertSort {
    public static void main(String[] args) {
        insertSort(new int[]{2, 34, 578, 13, 46, 7, 2, 6, 1, 7});
    }
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0 && array[j] > array[j+1]; j--) {
                swap(array, j, j+1);
            }
        }
        System.out.println(Arrays.toString(array));
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
